class Node:
    def __init__(self, value, stem = False):
        self.children = []
        self.value = value
        self.stem = stem

    def addElement(self, value):
        mini = min(self.value, value)
        maxi = max(self.value, value)
        if maxi % mini == 0:
            ret = False
            for child in self.children:
                ret = child.addElement(value) or ret 
            if not ret:
                self.children.append(Node(value))
            return True
        else:
            return False
    
    def getMaxPath(self):
        path = []
        for child in self.children:
            p = child.getMaxPath()
            if len(p) > len(path):
                path = p
        path.append(self.value)
        return path

class Solution(object):
    def largestDivisibleSubset(self, nums):
        """
        :type nums: List[int]
        :rtype: List[int]
        """
        nums.sort()
        root = Node(1, True)
        for num in nums:
            if num != 1:
                root.addElement(num)
        
        maxPath = root.getMaxPath()
        if 1 not in nums:
            maxPath.pop()
        maxPath.reverse()
        return maxPath